package easy;

import java.util.HashMap;
import java.util.Map;

/**
 * 面试题 17.10. 主要元素
 * 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。
 * 若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
 *
 * 示例 1：
 *
 * 输入：[1,2,5,9,5,9,5,5,5]
 * 输出：5
 * 示例 2：
 *
 * 输入：[3,2]
 * 输出：-1
 * 示例 3：
 *
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 * 通过次数68,200提交次数119,571
 */
public class M17_10_主要元素_L169_多数元素 {
    /**
     * 哈希表.
     *
     * 执行用时：13 ms, 击败了16.12%的用户
     * 内存消耗：43.6 MB, 击败了84.68%的用户
     */
    public int majorityElement(int[] nums) {
        if (nums.length == 1) return nums[0];
        int half = nums.length / 2;

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                int tmp = map.get(num) + 1;
                if (tmp > half) {
                    return num;
                } else {
                    map.put(num, tmp);
                }
            } else {
                map.put(num, 1);
            }
        }
        return -1;
    }

    /**
     * 摩尔投票法.
     *
     * 先随意选一个数字为candidate,如果下一个与其相等，count++, 否则count--
     * 如果count减为0了，则换candidate.
     *
     * 解答成功:
     * 执行耗时:1 ms,击败了99.95% 的Java用户
     * 内存消耗:44.3 MB,击败了46.69% 的Java用户
     */
    public int majorityElement2(int[] nums) {
        int candidate = -1;

        int count = 0;

        for (int num:nums){
            if (count == 0) {
                candidate = num;
            }

            if (candidate == num) {
                count++;
            } else {
                count--;
            }
        }

        count = 0;

        for (int num:nums){
            if (num == candidate) {
                count++;
            }
        }

        return count * 2 > nums.length ? candidate : -1;
    }


}
